<?php
/**
 * 稀疏图-邻接表
 */
class SparseGraph
{
    private $n;//点数
    private $m;//边数
    public $data;
    
    public $v;
    
    public $index;
    
    // false 有项图
    // true  无项图
    private $directed;
    
    /**
     * 初始化
     *
     * @param int  $n           点数
     * @param bool $directed    是否是无项图
     *
     * @return mixed
     */
    public function __construct(int $n,bool $directed)
    {
        $this->n = $n;
        $this->m = 0;
        $this->directed = $directed;
        
        for($i=0;$i<$n;$i++)
        {
            $this->data[$i] = [];
        }
    }
    
    
    public function V()
    {
        return $this->n;
    }
    public function E()
    {
        return $this->m;
    }
    
    /**
     * 增加边
     *
     * @param int $v 顶点v
     * @param int $w 顶点w
     *
     * @return mixed
     */
    public function addEdge(int $v,int $w)
    {
        array_push($this->data[$v],$w);
        
        //如果是无项图且是自环边
        if ( $v != $w &&!$this->directed)
        {
            array_push($this->data[$w],$v);
        }
        
        $this->m++;
    }
    
    /**
     * 判断两点之间是否存在平行边
     *
     * @param int $v 顶点v
     * @param int $w 顶点w
     *
     * @return boolean
     */
    public function hasEdge(int $v,int $w)
    {
        $count = $this->data[$v];
        for($i=0;$i<$count;$i++)
        {
            if ($this->data[$v][$i] == $w)
            {
                return true;
            }
        }
        return false;
    }
    
    
}


